// https://leetcode.cn/problems/wiggle-subsequence/

// 算法思路总结：
// 1. 使用贪心策略寻找最长摆动序列
// 2. 通过相邻元素差值判断摆动方向
// 3. 记录符号变化次数，相邻差值异号时计数
// 4. 最终长度为符号变化次数加1
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int m = nums.size();

        int ret = 0;
        int l = 0, r;
        for (int i = 0 ; i < m - 1 ; i++)
        {
            r = nums[i + 1] - nums[i];
            if (r == 0)
                continue;
            if (l * r <= 0)
            {
                ret++;
            }
            l = r;
        }

        return ret + 1;
    }
};

int main()
{
    vector<int> v1 = {1,7,4,9,2,5}, v2 = {1,17,5,10,13,15,10,5,16,8};
    Solution sol;

    cout << sol.wiggleMaxLength(v1) << endl;
    cout << sol.wiggleMaxLength(v2) << endl;

    return 0;
}